#include <iostream>
#include <vector>
using namespace std;
// 堆排序

// 向下调整
void adjust(int index, vector<int>& nums, int sz) {
    int l = index * 2 + 1, r = l + 1;
    int mx = index;
    if (l < sz && nums[l] > nums[mx]) mx = l;
    if (r < sz && nums[r] > nums[mx]) mx = r;
    swap(nums[index], nums[mx]);
    if (mx != index) adjust(mx, nums, sz);
}

void heapSort(vector<int>& nums) {
    int n = nums.size();
    // O(n-logn) 原地建堆
    for (int i = (n - 2) / 2; i >= 0; i--) adjust(i, nums, n);

    // 逐步调整，每次 O(log n), 调整 n 次
    for (int i = 0; i < n; i++) {
        swap(nums[0], nums[n - 1 - i]);
        adjust(0, nums, n - 1 - i);
    }
}
